package A一周刷爆LeetCode.A基础班.D详解桶排序以及排序内容大总结;

import A一周刷爆LeetCode.A基础班.B认识复杂度和简单排序算法.Sort;

/**
 * @author wei.zhao
 * @description: 基数排序
 * @date 2022年01月19日 16:41
 */
public class Code02_RadixSort extends Sort {

    @Override
    public void sort(int[] arr) {
        //数组最大值的位数
        int maxbits = maxbits(arr);
        //0-9的基数数组
        int[] radix;
        for (int i = 1; i <= maxbits; i++) {
            radix = new int[10];
            //遍历当前数组，求当前位数的值，对应的基数++
            for (int num : arr) {
                int digit = getDigit(num, i);
                radix[digit]++;
            }
            //基数数组，后面的等于前面的累加,计算当前位数所在的索引
            for (int i1 = 1; i1 < radix.length; i1++) {
                radix[i1] += radix[i1 - 1];
            }
            //倒序遍历当前数组，获取所处的索引位，添加到临时数组中
            int[] temp = new int[arr.length];
            for (int i1 = arr.length - 1; i1 >= 0; i1--) {
                int digit = getDigit(arr[i1], i);
                temp[radix[digit]-1] = arr[i1];
                radix[digit]--;
            }
            //将临时数组换入原数组
            for (int i1 = 0; i1 < temp.length; i1++) {
                arr[i1] = temp[i1];
            }
        }
    }

    //求数组最大值的位数
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            max = Math.max(i, max);
        }
        int i = 0;
        while (max != 0) {
            max = max / 10;
            i++;
        }
        return i;
    }

    //求数组第i位的数字
    public static int getDigit(int num, int i) {
        return (int) (num / (Math.pow(10, i - 1))) % 10;
    }

}
